/**
 * 项目名称: kruskal.cpp
 * 项目路径: study/DataStructure/数据结构/图/应用/最小生成树
 * 编辑时间: 2024年08月10日10时38分03秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

/**
 * kruskal算法:每次选择一条权值最小的边,使这条边的两头连通,(原本已经连通的就不选)直到所有结点都连通
 */

const int M = 100010;

struct Edge {
    int start;//起始点
    int end;//终止点
    int value;//权值
    //重载比较符号
    bool operator<(const Edge &Value) const {
        return value < Value.value;
    }
};

Edge edges[M];
int p[M];

/**
 * 并查集,返回祖宗节点,用以区分结点是否加入生成树
 * @param x
 * @return
 */
int find(int x) {
    if (p[x] != x)p[x] = find(p[x]);
    return p[x];
}

/**
 * kruskal算法
 * @param n 顶点数量
 * @param m 边数
 * @return
 */
int kruskal(int n, int m) {
    sort(edges, edges + m);//m是边的数量,排序
    for (int i = 1; i <= n; i++)p[i] = i;

    int res = 0;//代价
    int cnt = 0;//点数
    for (int i = 0; i < m; i++) {
        int start = edges[i].start;
        int end = edges[i].end;
        int value = edges[i].value;
        start = find(start);
        end = find(end);
        if (start != end) {//两个连通块不通,则将这两个连通块合并
            p[start] = end;
            res += value;
            cnt++;
        }
        if (cnt < n - 1)return -1;//不存在最小生成树
        return res;
    }
}

int main() {

    return 0;
}
